#include <iostream>
#include <stack>
#include <vector>
using namespace std;

//class Solution {
//public:
//    void returnPermute(vector<int>& num, vector<int>& r, int k, int n)
//    {
//
//        if (r.size() == n)
//        {
//            ret.push_back(r);
//            return;
//        }
//        for (int i = k; i < n; i++)
//        {
//            r.push_back(num[i]);
//            swap(num[i], num[k]);
//            returnPermute(num, r, k + 1, n);
//            swap(num[i], num[k]);
//            r.pop_back();
//        }
//    }
//
//    vector<vector<int> > permute(vector<int>& num) {
//        // write code here
//        int n = num.size();
//        vector<int> r;
//        returnPermute(num, r, 0, n);
//        return ret;
//    }
//    vector<vector<int> > ret;
//};
//
//
//class Solution {
//public:
//    int adp(int p, int q, char s)
//    {
//        switch (s)
//        {
//        case '+':
//            return p + q;
//        case '-':
//            return p - q;
//        case '*':
//            return p * q;
//        }
//        return 1;
//    }
//    int _solve(string s, int& i, int n)
//    {
//        stack<int> st1;
//        stack<char> st2;
//        while (i < n)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                int p = s[i] - '0';
//                while (i + 1 < n && (s[i + 1] >= '0' && s[i + 1] <= '9'))
//                {
//                    i++;
//                    p *= 10;
//                    p += s[i] - '0';
//                }
//                st1.push(p);
//            }
//            else if (s[i] == '+' || s[i] == '-')
//            {
//                st2.push(s[i]);
//            }
//            else if (s[i] == '*')
//            {
//                int p = st1.top();
//                st1.pop();
//                i++;
//                int q = 1;
//                if (s[i] == '(')
//                {
//                    i++;
//                    q = _solve(s, i, n);
//                }
//                else
//                {
//                    int px = s[i] - '0';
//                    while (i + 1 < n && (s[i + 1] >= '0' && s[i + 1] <= '9'))
//                    {
//                        i++;
//                        px *= 10;
//                        px += s[i] - '0';
//                    }
//                    q = px;
//                }
//                cout << p << " ";
//                cout << q << " ";
//                st1.push(p * q);
//            }
//            else if (s[i] == '(')
//            {
//                i++;
//                st1.push(_solve(s, i, n));
//            }
//            else if (s[i] == ')')
//            {
//                while (1)
//                {
//                    if (st2.empty())
//                    {
//                        break;
//                    }
//                    int p = st1.top();
//                    cout << p << " ";
//                    st1.pop();
//                    int q = st1.top();
//                    cout << q << " ";
//                    st1.pop();
//                    char s1 = st2.top();
//                    st2.pop();
//                    st1.push(adp(q, p, s1));
//                }
//                if (st2.empty())
//                {
//                    break;
//                }
//            }
//            i++;
//        }
//        while (!st2.empty())
//        {
//            char s1 = st2.top();
//            st2.pop();
//            int p = st1.top();
//            st1.pop();
//            int q = st1.top();
//            cout << p << " ";
//            cout << q << " ";
//            st1.pop();
//            st1.push(adp(q, p, s1));
//        }
//        return st1.top();
//    }
//    int solve(string s) {
//        // write code here
//        int n = s.size();
//        int i = 0;
//        return _solve(s, i, n);
//    }
//};


//class Solution {
//public:
//
//    int adp(int p, int q, char s)
//    {
//        switch (s)
//        {
//        case '+':
//            return p + q;
//        case '-':
//            return q - p;
//        case '*':
//            return p * q;
//        }
//        return 1;
//    }
//    int _solve(string s, int& i, int n)
//    {
//        stack<int> st1;
//        stack<char> st2;
//        while (i < n)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                int p = s[i] - '0';
//                while (i + 1 < n && (s[i + 1] >= '0' && s[i + 1] <= '9'))
//                {
//                    i++;
//                    p *= 10;
//                    p += s[i] - '0';
//                }
//                st1.push(p);
//            }
//            else if (s[i] == '+' || s[i] == '-')
//            {
//                st2.push(s[i]);
//            }
//            else if (s[i] == '*')
//            {
//                int p = st1.top();
//                st1.pop();
//                i++;
//                int q = 1;
//                if (s[i] == '(')
//                {
//                    i++;
//                    q = _solve(s, i, n);
//                }
//                else
//                {
//                    int px = s[i] - '0';
//                    while (i + 1 < n && (s[i + 1] >= '0' && s[i + 1] <= '9'))
//                    {
//                        i++;
//                        px *= 10;
//                        px += s[i] - '0';
//                    }
//                    q = px;
//                }
//                st1.push(p * q);
//            }
//            else if (s[i] == '(')
//            {
//                i++;
//                st1.push(_solve(s, i, n));
//            }
//            else if (s[i] == ')')
//            {
//                stack<int> st3;
//                while (!st1.empty())
//                {
//                    st3.push(st1.top());
//                    st1.pop();
//                }
//                stack<char> st4;
//                while (!st2.empty())
//                {
//                    st4.push(st2.top());
//                    st2.pop();
//                }
//                while (1)
//                {
//                    if (st4.empty())
//                    {
//                        break;
//                    }
//                    int p = st3.top();
//                    st3.pop();
//                    int q = st3.top();
//                    st3.pop();
//                    char s1 = st4.top();
//                    st4.pop();
//                    st3.push(adp(q, p, s1));
//                }
//                while (!st3.empty())
//                {
//                    st1.push(st3.top());
//                    st3.pop();
//                }
//                if (st4.empty())
//                {
//                    break;
//                }
//            }
//            i++;
//        }
//        stack<int> st3;
//        while (!st1.empty())
//        {
//            st3.push(st1.top());
//            st1.pop();
//        }
//        stack<char> st4;
//        while (!st2.empty())
//        {
//            st4.push(st2.top());
//            st2.pop();
//        }
//        while (!st4.empty())
//        {
//            char s1 = st4.top();
//            st4.pop();
//            int p = st3.top();
//            st3.pop();
//            int q = st3.top();
//            st3.pop();
//            st3.push(adp(q, p, s1));
//        }
//        return st3.top();
//    }
//    int solve(string s) {
//        // write code here
//        int n = s.size();
//        int i = 0;
//        return _solve(s, i, n);
//    }
//};

//int main()
//{
//    string s = "((10+2)*10-(100-(10+20*10-(2*3)))*10*1*2)-2";
//    Solution s1;
//    s1.solve(s);
//    return 0;
//}

//class Solution {
//public:
//    int minCostClimbingStairs(vector<int>& cost) {
//        // write code here
//        int n = cost.size();;
//        int* num = new int[n];
//        num[0] = cost[0];
//        num[1] = cost[1];
//        for (int i = 2; i < n; i++)
//        {
//            num[i] = min(num[i - 1], num[i - 2]) + cost[i];
//        }
//        return min(num[n - 1], num[n - 2]);
//    }
//};

//class Solution {
//public:
//    void Sort_solve(string& nums, int& n, int i)
//    {
//        if (n == i)
//        {
//            chat++;
//            return;
//        }
//        if (nums[i] == '0')
//        {
//            return;
//        }
//        else if (i + 1 < n && nums[i] == '1' && nums[i + 1] != '0')
//        {
//            Sort_solve(nums, n, i + 1);
//            Sort_solve(nums, n, i + 2);
//        }
//        else if (i + 2 < n && (nums[i] == '2') && nums[i + 1] < '7' && nums[i + 1]>'0')
//        {
//            Sort_solve(nums, n, i + 1);
//            Sort_solve(nums, n, i + 2);
//        }
//        else if (i + 1 < n && nums[i] == '1' && nums[i + 1] == '0')
//        {
//            Sort_solve(nums, n, i + 2);
//        }
//        else if (i + 2 < n && (nums[i] == '2') && nums[i + 1] == '0')
//        {
//            Sort_solve(nums, n, i + 2);
//        }
//        else
//        {
//            Sort_solve(nums, n, i + 1);
//        }
//    }
//    int solve(string nums) {
//        // write code here
//        int n = nums.size();
//        int i = 0;
//        Sort_solve(nums, n, i);
//        return chat;
//    }
//    int chat = 0;
//};
//
//#include <algorithm>
//class Solution {
//public:
//    void returnPermute(vector<int>& num, vector<int>& r, int k, int n)
//    {
//
//        if (r.size() == n)
//        {
//            ret.push_back(r);
//            return;
//        }
//        for (int i = k; i < n; i++)
//        {
//            r.push_back(num[i]);
//            swap(num[i], num[k]);
//            returnPermute(num, r, k + 1, n);
//            swap(num[i], num[k]);
//            r.pop_back();
//        }
//    }
//    vector<vector<int> > permuteUnique(vector<int>& num) {
//        // write code here
//        int n = num.size();
//        vector<int> r;
//        returnPermute(num, r, 0, n);
//        sort(ret.begin(), ret.end());
//        ret.erase(unique(ret.begin(), ret.end()), ret.end());
//        return ret;
//    }
//    vector<vector<int> > ret;
//};

class Solution {
public:
    int solve(string nums) {
        // write code here
        if (nums[0] == '0')
        {
            return 0;
        }
        int n = nums.size();
        if (n == 1)
        {
            return 1;
        }
        vector<int> str(n + 1, 1);
        for (int i = 2; i <= n; i++)
        {
            if (nums[i - 1] == '0' && (nums[i - 2] != '1' && nums[i - 2] != '2'))
            {
                return 0;
            }
            if (nums[i - 1] != '0' && (nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] < '7')))
            {
                str[i] = str[i - 1] + str[i - 2];
            }
            else
            {
                str[i] = str[i - 1];
            }
        }
        return str[n];
    }
};

int main()
{
    string s = "10";
    Solution s1;
    s1.solve(s);
    return 0;
}